package leecode

func findTargetSumWays(nums []int, target int) int {
	sum := 0
	for i := 0; i < len(nums); i++ {
		sum += nums[i]
	}
	if sum < target || -target > sum || (target+sum)%2 == 1 {
		return 0
	}
	positive := (target + sum) / 2 //正数的集合
	dp := make([]int, positive+1)  //装满容量为j的背包有多少种方法
	dp[0] = 1
	for i := 0; i < len(nums); i++ {
		// 背包容量要大于当前物品重量
		for j := positive; j >= nums[i]; j-- {
			dp[j] += dp[j-nums[i]]
		}
	}
	return dp[positive]
}
